package com.nl.list;

public class ComplexedLinkedList<T> {

	public static class Node<T> {
		Node<T> next;
		Node<T> sibling;
		T value;
		
		public void set(Node<T> next,Node<T> sibling,T value){
			this.next = next;
			this.sibling = sibling;
			this.value = value;
		}
	}
	
	Node<T> phead;
	
	public ComplexedLinkedList<T> cloneLinkedList(){
		cloneNodes(this.phead);
		connectSiblings(this.phead);
		Node<T> cloneHead = reconnectNodes(this.phead);
		ComplexedLinkedList<T> cloneList = new ComplexedLinkedList<T>();
		cloneList.phead = cloneHead;
		return cloneList;
	}

	//复制节点到当前链表
	private void  cloneNodes(Node<T> phead) {
		Node<T> node = phead;
		while(node!=null){
			Node<T> cloneNode = new Node<T>();
			cloneNode.value  = node.value;
			cloneNode.next = node.next;
			node.next = cloneNode;
			node = cloneNode.next;
		}
	}
	
	private void connectSiblings(Node<T> phead){
		Node<T> node = phead;
		while(node!=null){
			if(node.sibling!=null){
				node.next.sibling=node.sibling.next;
			}
			node = node.next.next;
		}
	}
	
	//将基数位置的节点进行链接，偶数位置的节点进行链接
	private Node<T> reconnectNodes(Node<T> phead){
		Node<T> node = phead;
		Node<T> cloneHead = null;
		Node<T> cloneNode = null;
		if(node!=null){
			cloneNode = cloneHead  = node.next;
			//先连接node,防止空指针
			//一个节点
			node.next = cloneNode.next;
			node = cloneNode.next;
		}
		//easy　null pointer
		// A -> A' -> B -> B'
		// A -> A'
		while(node!=null){
			cloneNode.next  = node.next;
			cloneNode=node.next;
			node.next = cloneNode.next;
			node = cloneNode.next;
		}
		return cloneHead;
	}

	public static void main(String[] args) {

		Node<Integer> a = new Node<Integer>();
		Node<Integer> b = new Node<Integer>();
		Node<Integer> c = new Node<Integer>();
		Node<Integer> d = new Node<Integer>();
		
		a.set(b, d, 1);
		b.set(c, a, 2);
		c.set(d, b, 3);
		d.set(null, a, 4);

		ComplexedLinkedList<Integer> list = new ComplexedLinkedList<Integer>();
		list.phead  =a ;
		
		ComplexedLinkedList<Integer>cloneList = list.cloneLinkedList();
		Node<Integer>cloneHead= cloneList.phead;
		System.out.println(cloneHead.next.value);
		System.out.println(cloneHead.value);
		System.out.println(cloneHead.next.sibling.value);

	}
};
